#include<iostream>
#include<vector>
using namespace std;
struct data_str
{
    //int num[30][30];
    int weight;
	int next;
	int day;
};
//vector <data_str>  N[30];
data_str N[30][30];
int FMultiGraph(int k,int*p,int n)	     
{   
    float *cost=new float[n]; 
    int *d=new int[n];        
    int *c=new int[n];		  
    for(int i=0;i<n;i++)	cost[i]=0;
    for (int j=0;j<=n-1;j++) 	
		for (int r=0;r<sizeof(N[j]);r++) 
			if (N[j][r].weight+cost[j]>cost[N[j][r].next]) 
			{
				cost[N[j][r].next]=N[j][r].weight+cost[j]; 
				d[N[j][r].next]=j;			
				c[N[j][r].next]=N[j][r].day;
			}
				

    int ans=cost[n-1]; 	
    int tem=n-1;
    for(int i=k;i>0;i--) 
    {
    	p[i]=c[tem];
    	tem=d[tem];
	}
    delete []cost;
    delete []d;
    delete []c;
    return ans;
}
int main()
{
	int k=5;
	int n=18;
	int p[105];
	int w[4][4]={4,4,5,8,
				3,5,6,7,
				5,6,8,8,
				2,4,7,8};
	for(int i=1;i<5;i++)
	{
		data_str tem={w[0][i-1],i,i};
		N[0].push_back(tem);
	}
	int tem=0;
	for(int i=0;i<3;i++)
		for(int j=1;j<=4;j++)
			for(int k=j;k<=4;k++)
			{
				data_str tem={w[i+1][k-j],i*4+j+k-j+4,k-j+1};
				N[i*4+j].push_back(tem);
			}
	for(int i=13;i<17;i++)
	{
		data_str tem={0,17,0};
		N[i].push_back(tem) ;
	}

	cout<<"最大收益为："<<FMultiGraph(k,p,n)<<endl;
	for(int i=1;i<k;i++)
		cout<<"第"<<i<<"阶段使用"<<p[i]<<"天"<<endl; 
	return 0;
}
